package 剑指offer.数组;

/**
 * 给一个数组，返回它的最大连续子序列的和。要求O（n）
 */
public class 第42题连续子数组的最大和 {

    /*
    最直观的方法是列举全部的子数组，然后求出和最大的那个就行了。
    但是要求必须是 O（n），那就只能遍历一次了
    以一组数据为例简单分析：1,-2,3,10,-4,7,2,-5
    来一个 1，sum = 1
    来一个 -2，sum = -1
    来一个 3，sum = 2（sum 虽然大于 -1 了，但是我加了一个 3 结果总和却变成了 2，那这个 3 加的意义何在？？）
    所以前面的子数组不和要求。丢弃。从 3 重新开始
    3, sum = 3
    10 sum = 13
    -4 sum = 9（sum 在减少，此时不更新 sum，继续往下走）
    7 sum = 16（说明之前的 -4 没啥影响）
    2 sum = 18
    -5 sum = 13（遍历结束，sum = 18）
     */
    public static int FindGreatestSumOfSubArray(int[] array) {
        int sum = Integer.MIN_VALUE;
        int tmpSum = 0;
        if (array == null || array.length == 0)
            return sum;
        for (int i = 0; i < array.length; i++) {
            // 越加越小，tmpSum 要重新开始
            if (tmpSum <= 0) {
                tmpSum = array[i];
            } else {
                tmpSum += array[i];
            }
            // 如果加了一个数后总和比加的这个数要小
            if (tmpSum > sum) {
                sum = tmpSum;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
//        int[] arr = {1, -2, 3, 10, -4, 7, 2, -5};
        int[] arr = {-2, -8, -1, -5, -9};
        System.out.println(FindGreatestSumOfSubArray(arr));
        System.out.println(0x80000000);
    }
}
